package com.leetcode.array_matrix;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author Dennis Li
 * @date 2020/10/26 18:24
 */
public class SmallerNumbersThanCurrent_1365 {

    public int[] smallerNumbersThanCurrent(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        for (int i = nums.length - 1; i >= 0; i--) {
            // 考虑到有相同的情况，反着遍历，最后复制的一定是相等值的最小位置
            map.put(sorted[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            // 可以直接修改原数组
            nums[i] = map.get(nums[i]);
        }
        return nums;
    }

    public int[] smallerNumbersThanCurrent2(int[] nums) {
        // 计数方法
        // 记录出现的次数
        // 范围使 0 ~ 100
        int[] counts = new int[101], pre = new int[101];
        for (int num : nums) {
            counts[num]++;
        }
        // 在第i位，计算 0 ~ i - 1的前缀和
        for (int i = 1; i <= 100; i++) {
            pre[i] = pre[i - 1] + counts[i - 1];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = pre[nums[i]];
        }
        return nums;
    }

}
